package basic.study.wantOffer.chapter2;

/**
 * @author Kevin
 * @date 2020/4/28 22:18
 * 二叉树的下一个节点
 * 给定一颗二叉树和其中一个点，找出中序遍历时的下一个节点
 * 情况1.有右子树    2.1 无右子树且节点为其父节点的左子节点   2.2无右子树且节点为其父节点的右子节点
 */
public class Problem8 {

    Node GetNext(Node node) {
        if (node == null) return null;

        Node next = null;
        if (node.right != null) {
            Node right = node.right;
            while (right.left != null) {
                right = right.left;
            }
            next = right;
        } else if (node.parent != null) {
            Node cur = node;
            Node parent = node.parent;
            while (parent != null && cur == parent.right) {
                cur = parent;
                parent = parent.parent;
            }
            next = parent;
        }

        return next;
    }


    class Node {
        Node parent;
        Node left;
        Node right;
    }
}
